package dynamicProgramming.MatrixPathProblem;

/**
 * @author zxc
 * @date 2023/01/24 17:22
 **/

import java.util.List;

/**
 * 题目 ：三角形中的最小路径之和
 * 题目详述 ：
 * 给定一个三角形 triangle ，找出自顶向下的最小路径和。
 * 每一步只能移动到下一行中相邻的结点上。
 * 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
 * 也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
 *
 * 提示：
 * 1 <= triangle.length <= 200
 * triangle[0].length == 1
 * triangle[i].length == triangle[i - 1].length + 1
 * -104 <= triangle[i][j] <= 104
 *
 */
public class MinimumTotal {
    /**
     * 思路 ：
     * 假设f(i,j)表示为从三角形顶部（0，0）出发，到达三角形行号和列号分别为i和j的坐标（i，j）的最小路径之和;
     *
     * 状态转移方程 ：
     * 即，要求解的f(i,j)的话,则需要f(i-1,j-1)和f(i-1,j)进行辅助求解;
     * 1.特殊情况 ：
     * （1）j == 0 ：
     * f(i,j) = f(i-1,j) + triangle[i][j];
     * （2）i == j ：
     * f(i,j) = f(i-1,j-1) + triangle[i][j];
     * 2.一般情况 ：
     * f(i,j) = Math.min(f(i-1,j-1),f(i-1,j)) + triangle[i][j];
     *
     * @param triangle
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        int len = triangle.size();
        // 即，要求解的f(i,j)的话,则需要f(i-1,j-1)和f(i-1,j)进行辅助求解;
        // ===> 只需要2行n列数组，就能够对于f(i,j)进行求解;
        int[][] temp = new int[2][len];
        for(int i = 0; i < len; i++){
            // 由于所要求取的是三角形最小路径之和，所以必须满足 j <= i;
            for(int j = 0; j <= i; j++){
                // 主要针对于i == 0的情况，在for内层循环中进行初始化;
                // 需要注意的是，同时会获取到triangel集合中当前正在遍历的(i,j)值;
                temp[i % 2][j] = triangle.get(i).get(j);
                // temp[i % 2][j]中所存储的值为 当前f(i,j)在triangle集合中所对应的元素值triangle(i,j);
                // 即，temp[i % 2][j]用来存储当前值triangle(i,j);
                if(i > 0){
                    // 特殊情况1 ：当j == 0时，即只存在f(i-1,j)所对应的triangle元素，而不存在f(i-1,j-1)所对应的triangle元素;
                    if(j == 0){
                        temp[i % 2][j] += temp[(i - 1) % 2][j];
                    }
                    // 特殊情况2 ：当i == j时，即不存在f(i-1,j)所对应的triangle元素，只存在f(i-1,j-1)所对应的triangle元素;
                    else if(i == j){
                        temp[i % 2][j] += temp[(i - 1) % 2][j - 1];
                    }
                    // 一般情况 ：
                    else {
                        temp[i % 2][j] += Math.min(temp[(i - 1)% 2][j], temp[(i - 1) % 2][j - 1]) ;
                    }
                }
            }
        }
        // 即，对于任意j的值，temp[(len - 1) % 2][j]都可能为三角形的路径之和
        // ===》 即，需要对于其相互之间进行比较，从而使得三角形的最小路径之和;
        int minValue = Integer.MAX_VALUE;
        for (int num : temp[(len - 1) % 2]) {
            //
            minValue = Math.min(minValue , num);
        }
        return minValue;
    }
}
